<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<HTML
><HEAD
><TITLE
>Planner/Optimizer</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.79"><LINK
REV="MADE"
HREF="mailto:pgsql-docs@postgresql.org"><LINK
REL="HOME"
TITLE="PostgreSQL 9.1.2 Documentation"
HREF="index.html"><LINK
REL="UP"
TITLE="Overview of PostgreSQL Internals"
HREF="overview.html"><LINK
REL="PREVIOUS"
TITLE="The PostgreSQL Rule System"
HREF="rule-system.html"><LINK
REL="NEXT"
TITLE="Executor"
HREF="executor.html"><LINK
REL="STYLESHEET"
TYPE="text/css"
HREF="stylesheet.css"><META
HTTP-EQUIV="Content-Type"
CONTENT="text/html; charset=ISO-8859-1"><META
NAME="creation"
CONTENT="2011-12-01T22:07:59"></HEAD
><BODY
CLASS="SECT1"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="5"
ALIGN="center"
VALIGN="bottom"
><A
HREF="index.html"
>PostgreSQL 9.1.2 Documentation</A
></TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
TITLE="The PostgreSQL Rule System"
HREF="rule-system.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="top"
><A
HREF="overview.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="60%"
ALIGN="center"
VALIGN="bottom"
>Chapter 44. Overview of PostgreSQL Internals</TD
><TD
WIDTH="20%"
ALIGN="right"
VALIGN="top"
><A
TITLE="Executor"
HREF="executor.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="PLANNER-OPTIMIZER"
>44.5. Planner/Optimizer</A
></H1
><P
>    The task of the <I
CLASS="FIRSTTERM"
>planner/optimizer</I
> is to
    create an optimal execution plan. A given SQL query (and hence, a
    query tree) can be actually executed in a wide variety of
    different ways, each of which will produce the same set of
    results.  If it is computationally feasible, the query optimizer
    will examine each of these possible execution plans, ultimately
    selecting the execution plan that is expected to run the fastest.
   </P
><DIV
CLASS="NOTE"
><BLOCKQUOTE
CLASS="NOTE"
><P
><B
>Note: </B
>     In some situations, examining each possible way in which a query
     can be executed would take an excessive amount of time and memory
     space. In particular, this occurs when executing queries
     involving large numbers of join operations. In order to determine
     a reasonable (not necessarily optimal) query plan in a reasonable amount
     of time, <SPAN
CLASS="PRODUCTNAME"
>PostgreSQL</SPAN
> uses a <I
CLASS="FIRSTTERM"
>Genetic
     Query Optimizer</I
> (see <A
HREF="geqo.html"
>Chapter 51</A
>) when the number of joins
     exceeds a threshold (see <A
HREF="runtime-config-query.html#GUC-GEQO-THRESHOLD"
>geqo_threshold</A
>).
    </P
></BLOCKQUOTE
></DIV
><P
>    The planner's search procedure actually works with data structures
    called <I
CLASS="FIRSTTERM"
>paths</I
>, which are simply cut-down representations of
    plans containing only as much information as the planner needs to make
    its decisions. After the cheapest path is determined, a full-fledged
    <I
CLASS="FIRSTTERM"
>plan tree</I
> is built to pass to the executor.  This represents
    the desired execution plan in sufficient detail for the executor to run it.
    In the rest of this section we'll ignore the distinction between paths
    and plans.
   </P
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="AEN84077"
>44.5.1. Generating Possible Plans</A
></H2
><P
>     The planner/optimizer starts by generating plans for scanning each
     individual relation (table) used in the query.  The possible plans
     are determined by the available indexes on each relation.
     There is always the possibility of performing a
     sequential scan on a relation, so a sequential scan plan is always
     created. Assume an index is defined on a
     relation (for example a B-tree index) and a query contains the
     restriction
     <TT
CLASS="LITERAL"
>relation.attribute OPR constant</TT
>. If
     <TT
CLASS="LITERAL"
>relation.attribute</TT
> happens to match the key of the B-tree
     index and <TT
CLASS="LITERAL"
>OPR</TT
> is one of the operators listed in
     the index's <I
CLASS="FIRSTTERM"
>operator class</I
>, another plan is created using
     the B-tree index to scan the relation. If there are further indexes
     present and the restrictions in the query happen to match a key of an
     index, further plans will be considered.  Index scan plans are also
     generated for indexes that have a sort ordering that can match the
     query's <TT
CLASS="LITERAL"
>ORDER BY</TT
> clause (if any), or a sort ordering that
     might be useful for merge joining (see below).
    </P
><P
>     If the query requires joining two or more relations,
     plans for joining relations are considered
     after all feasible plans have been found for scanning single relations.
     The three available join strategies are:

     <P
></P
></P><UL
><LI
><P
>        <I
CLASS="FIRSTTERM"
>nested loop join</I
>: The right relation is scanned
        once for every row found in the left relation. This strategy
        is easy to implement but can be very time consuming.  (However,
        if the right relation can be scanned with an index scan, this can
        be a good strategy.  It is possible to use values from the current
        row of the left relation as keys for the index scan of the right.)
       </P
></LI
><LI
><P
>        <I
CLASS="FIRSTTERM"
>merge join</I
>: Each relation is sorted on the join
        attributes before the join starts. Then the two relations are
        scanned in parallel, and matching rows are combined to form
        join rows. This kind of join is more
        attractive because each relation has to be scanned only once.
        The required sorting might be achieved either by an explicit sort
        step, or by scanning the relation in the proper order using an
        index on the join key.
       </P
></LI
><LI
><P
>        <I
CLASS="FIRSTTERM"
>hash join</I
>: the right relation is first scanned
        and loaded into a hash table, using its join attributes as hash keys.
        Next the left relation is scanned and the
        appropriate values of every row found are used as hash keys to
        locate the matching rows in the table.
       </P
></LI
></UL
><P>
    </P
><P
>     When the query involves more than two relations, the final result
     must be built up by a tree of join steps, each with two inputs.
     The planner examines different possible join sequences to find the
     cheapest one.
    </P
><P
>     If the query uses fewer than <A
HREF="runtime-config-query.html#GUC-GEQO-THRESHOLD"
>geqo_threshold</A
>
     relations, a near-exhaustive search is conducted to find the best
     join sequence.  The planner preferentially considers joins between any
     two relations for which there exist a corresponding join clause in the
     <TT
CLASS="LITERAL"
>WHERE</TT
> qualification (i.e., for
     which a restriction like <TT
CLASS="LITERAL"
>where rel1.attr1=rel2.attr2</TT
>
     exists). Join pairs with no join clause are considered only when there
     is no other choice, that is, a particular relation has no available
     join clauses to any other relation. All possible plans are generated for
     every join pair considered by the planner, and the one that is
     (estimated to be) the cheapest is chosen.
    </P
><P
>     When <TT
CLASS="VARNAME"
>geqo_threshold</TT
> is exceeded, the join
     sequences considered are determined by heuristics, as described
     in <A
HREF="geqo.html"
>Chapter 51</A
>.  Otherwise the process is the same.
    </P
><P
>     The finished plan tree consists of sequential or index scans of
     the base relations, plus nested-loop, merge, or hash join nodes as
     needed, plus any auxiliary steps needed, such as sort nodes or
     aggregate-function calculation nodes.  Most of these plan node
     types have the additional ability to do <I
CLASS="FIRSTTERM"
>selection</I
>
     (discarding rows that do not meet a specified Boolean condition)
     and <I
CLASS="FIRSTTERM"
>projection</I
> (computation of a derived column set
     based on given column values, that is, evaluation of scalar
     expressions where needed).  One of the responsibilities of the
     planner is to attach selection conditions from the
     <TT
CLASS="LITERAL"
>WHERE</TT
> clause and computation of required
     output expressions to the most appropriate nodes of the plan
     tree.
    </P
></DIV
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="rule-system.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="index.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="executor.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>The <SPAN
CLASS="PRODUCTNAME"
>PostgreSQL</SPAN
> Rule System</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="overview.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Executor</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>